P6055 [RC-02] GCD

这道题的反推还是挺有意思的。

i=1nj=1np=1njq=1nj[(i,j)=1][(p,q)=1]\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

阅读全文 »

SP26108 TRENDGCD - Trending GCD

i=1nj=1mij(i,j)μ2((i,j))\sum_{i=1}^n\sum_{j=1}^m ij (i,j)\mu^2((i,j))

k=1min(n,m)i=1nj=1m[(i,j)=k]ijkμ2(k)\sum_{k=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m [(i,j)=k]ij k\mu^2(k)

阅读全文 »

P3977 [TJOI2015]棋盘

你得知道题目下表是从 00 开始编号,那么每个棋子只能控制与它距离不大于 11 的行。

所以只需压当前这一行的状态,令 dp(i,S)dp(i,S) 表示前 ii 行棋子,第 ii 的摆放状态为 SS 的方案。

那么有转移:

阅读全文 »

CF208E Blood Cousins

uu 拥有共同的 kk 级祖先的点数就是 uukk 级祖先的 kk 级儿子的数量 1-1.

再转换一下就是以 uukk 级祖先为根的子树内深度为 depu+kdep_u+k 的点的个数1-1

然后用 cntdcnt_d 表示深度为 dd 的点数,直接 dsu on tree\text{dsu~on~tree} 即可。

阅读全文 »